// 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
// 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
// 返回获得利润的最大值。
// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

export const maxProfit = function (prices: number[], fee: number): number {
    // 定义状态变量：
    // dpB表示当天如果买入可以获得的最大收益，初始化为第一天买入
    // dpS表示当天如果卖出可以获得的最大收益，初始化为0（第一天没股票可卖）
    let dpBuy: number = -prices[0];
    let dpSell: number = 0;
    for (let i = 1; i < prices.length; i++) {
        let preBuy: number = dpBuy;
        let preSell: number = dpSell;
        // 状态转移方程
        dpBuy = Math.max(preBuy, preSell - prices[i]);
        dpSell = Math.max(preSell, preBuy + prices[i] - fee);
    }
    return dpSell;
};


maxProfit([1, 3, 7, 5, 10, 3], 3)

// 这道题目也是非常典型的采用动态规划求解的题目了
// 首先这里要想到正确的定义状态：对于每一天来讲，只有两种状态可选，卖股票或者持有股票（持有股票包括了当天买入的情况）
// dpB表示当前天卖出股票可获得的最大利润
// dpS表示持有可获得的最大利润（注意是持有，而不仅仅是买入）。
// 对于状态转移方程，还算比较好想：
// 对于今天卖出股票的情况：可以从以下两个状态转移过来：
// 1. 昨天也不持有；2. 昨天持有，今天卖出；我们对两者取较大值。
// 对于今天持有股票的情况：可以从以下两个状态转移过来：
// 1. 昨天也持有；2. 昨天不持有股票，今天买入；两者取较大值。
// 而对于状态存储，只需要两个变量，一遍扫描即可。